using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Threading.Tasks;

namespace DataStructure
{
    /// <summary>
    /// 基于链表实现哈希表
    /// </summary>
    /// <typeparam name="Key"></typeparam>
    public class HashST1<Key>
    {
        /// <summary>
        /// 每个位置都指向一条链表,将冲突的元素都存在链表中
        /// </summary>
        private LinkedList1<Key>[] hashtable;  
        private int count; // 存储的元素个数
        private int size; // 哈希表的大小
        
        public HashST1(int size)
        {
            this.size = size;
            count = 0;
            hashtable = new LinkedList1<Key>[size]; 
            for (int i = 0; i < size; i++)
                hashtable[i] = new LinkedList1<Key>();
        }
        
        public HashST1() : this(97) {}
        
        public int Count => count;
        public bool IsEmpty => count == 0;
        
        /// <summary>
        /// 将键转化为数组的索引
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        private int Hash(Key key)
        {
            //获取哈希码,与0x7fffffff相与,防止负数，再对数组大小取模得到索引
            return (key.GetHashCode() & 0x7fffffff) % size;
        }
        
        /// <summary>
        /// 添加元素
        /// 不允许有重复值
        /// </summary>
        /// <param name="key"></param>
        public void Add(Key key)
        {
            LinkedList1<Key> list = hashtable[Hash(key)];
            if(list.Contains(key))
                return;
            else
            {
                list.AddFirst(key);
                count++;
            }
        }
        
        public void Remove(Key key)
        {
            LinkedList1<Key> list = hashtable[Hash(key)];
            if (list.Contains(key))
            {
                list.Remove(key);
                count--;
            }
        }
        
        public bool Contains(Key key)
        {
            return hashtable[Hash(key)].Contains(key);
        }
    }
}   